package com.hpeu_12.day1223;

import java.util.Arrays;

/**
 * 二分法查找算法
 *使用二分法查找算法的前提是：被查找的数组已经排好序
 *
 *算法描述：把数组中的元素，从小到大有序的存放进数组中，首先将给定值与数组中间位置的值作比较，
 *如果相等，则匹配成功。否则，若比较值小了，则在数组的前半部分继续进行二分查找，若比较的值大了，
 *则在数组的后半部分进行二分查找。如此循环往复，直到比较的值与中间的值匹配，完成查找
 *
 */
public class BinarySearch {

	public static void main(String[] args) {
		int[] arr = {30,80,9,7,12,100,40,8};
		//二分查找之前，一定要保证数组是排好序的。
		Arrays.sort(arr);
		System.out.println(Arrays.toString(arr));
		//定义要查找的数
		int searchNumber = 100;
		//开始位置
		int low = 0;
		//结束位置
		int high = arr.length - 1;
		
		//定义一个boolean 类型的变量用于判断是否找到元素
		boolean flag = true;
		while(low <= high) {
			int middle = (low+high)/2;
			if (searchNumber == arr[middle]) {
				System.out.println("您查找的元素的索引为："+middle);
				flag = false;
				break;
			}
			if (searchNumber > arr[middle]) {
				low = middle+1;
			}
			if (searchNumber < arr[middle]) {
				high = middle -1;
			}
		}
		if (flag) {
			System.out.println("对不起，没找到元素！");
		}
	}

}
